﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 原题连接：https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&ru=/exam/oj

/*
题目描述：
描述
现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

要求：空间复杂度
𝑂
(
1
)
O(1)，时间复杂度
𝑂
(
𝑛
𝑙
𝑜
𝑔
𝑛
)
O(nlogn)，本题也有时间复杂度
𝑂
(
𝑛
)
O(n) 的解法
输入描述：
输入五张扑克牌的值
返回值描述：
五张扑克牌能否组成顺子。
示例1
输入：
[6,0,2,0,4]
复制
返回值：
true
复制
说明：
中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
这样这五张牌在[2,6]区间连续，输出true
示例2
输入：
[0,3,2,6,4]
复制
返回值：
true
复制
示例3
输入：
[1,0,0,1,0]
复制
返回值：
false
复制
示例4
输入：
[13,12,11,0,1]
复制
返回值：
false

*/

// 开始解题：
// 方法——排序
class Solution {
public:
    bool IsContinuous(vector<int>& nums) {
        int n = nums.size();
        int zero = 0;
        // 先算出0的个数
        for (auto x : nums) {
            if (!x) {
                zero++;
            }
        }
        // 排序
        sort(nums.begin(), nums.end());
        int cnt = 0;
        // 算出缺多少个数
        for (int i = 1; i < n; i++) {
            if (nums[i] != 0 && nums[i - 1] != 0) {
                if (nums[i] == nums[i - 1]) {
                    return false;
                }
                cnt += nums[i] - nums[i - 1] - 1;
            }
        }
        return zero >= cnt; // 只要0能补上缺少的数，就能凑成顺子
    }
};